#! /usr/bin/python

import math
import time
import random
tt = time.time()

print 10 + 315410 + 927070 + 2525870 + 8146100 + 16755190 + 39313460 + 97387280 + 119571820 + 121288430 + 130116970 + 139985660
_mrpt_num_trials = 5

def tryComposite(a, s, d, n):
    x = pow(a, d, n)
    if x == 1: return False
    for i in range(s):
	x = pow(a, 2**i * d, n)
	if x == n - 1: return False
    return True

def millerRabin(n):
    s = 0
    d = n - 1
    while(d%2 == 0):
         s += 1
	 d /= 2
    k = 0
    for i in range(_mrpt_num_trials):
	a = random.randrange(2, n)
        if tryComposite(a, s, d, n): return False
    return True

print millerRabin(25)
    
def isPrime(n):
    if n ==2 or n==3 or n==5 or n==7: return True
    if n==1 or n%2 == 0 or n%3 == 0: return False
    for i in range(5, int(math.sqrt(n))+1, 6):
        if n%i == 0 or n%(i+2) == 0: return False
    return True

def sieve(n):
    ll = range(n)
    for i in range(2, int(math.sqrt(n)) + 1):
	for j in range(i**2, n, i):
	    ll[j] = 0
    return [p for p in ll if p != 0]

ll = sieve(13*10**3)
ll.remove(1)
ll.remove(2)
print ll[0:10]
ss = 0
nlist = []
for n in range(10, 150*10**6, 10):    
    if n%3 == 0 or n%7 == 0 or n%13 == 0: continue
    flag = True
    for p in ll:
 	for s in (1, 3, 7, 9, 13, 27):
	    if ((n%p)**2 + s)%p == 0: 
		flag = False
		break
	if flag == False: break
    if flag == True: 
	#print n
	nlist.append(n)

print len(nlist)

for i in nlist:
    sn = i**2
    if millerRabin(sn + 1) and millerRabin(sn + 3) and millerRabin(sn + 7) and millerRabin(sn + 9) and millerRabin(sn + 13) and millerRabin(sn + 27) and millerRabin(sn + 17) == False and millerRabin(sn + 19) == False and millerRabin(sn + 21) == False and millerRabin(sn + 23) == False:
	#print i
	ss += i


print ss

print time.time() - tt
